package main.java.indi.zyj.hot100;

import main.java.indi.zyj.hot100.base.ListNode;

public class _29_sortList {

    public ListNode sortList(ListNode head) {

        if (head == null || head.next == null) {
            return head;
        }

        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode mid = slow.next;
        slow.next = null;

        ListNode p1 = sortList(head);
        ListNode p2 = sortList(mid);
        ListNode top = new ListNode(0);
        ListNode p = top;
        
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }

        p.next = p1 != null ? p1 : p2;
        
        return top.next;
        
    }
}
